package com.leetcode;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        String str = "aababacsfaba";
        //暴力解法
        System.out.println(longestPalindrome(str));
        //中心扩展方法
        System.out.println(longestPalindrome1(str));
    }
    /**
     * 中心扩展方法：
     * 将每一个字符当作回文的中心，向两边扩展，当回文字符串的长度为偶数时，中心为两个字符。
     */
    public static String longestPalindrome1(String str){
        int len = str.length();
        int max = 0;
        int start_index = 0;
        for (int i = 0; i < len; i++) {
            int len1 = expandAroundCenter(str,i,i);
            int len2 = expandAroundCenter(str,i,i+1);
            int temp = Math.max(len1,len2);
            if (max < temp) {
                max = temp;
                start_index = i - (max - 1) / 2;
            }
        }
        return str.substring(start_index,start_index + max);
    }
    public static int expandAroundCenter(String s,int left,int right){
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right - left - 1;
    }

    /**
     * 时间复杂度高，空间复杂度高
     * @param str
     * @return
     */
    public static String longestPalindrome(String str) {
        int len = str.length();
        int max = 0;
        int index = 0;
        /**
         * dp[i][j] 表示 从i到j是否是回文字符串，这里i，j均为索引
         */
        boolean[][] dp = new boolean[len][len];
        for (int i = len; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (str.charAt(j) != str.charAt(i)){
                    continue;
                }
                //当str.charAt(j) == str.charAt(i)时，j - i <= 2的情况均为回文
                //dp[i][j]想要是回文，仅当 dp[i + 1][j - 1]为回文
                dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
                if (dp[i][j]){
                    //记录最大的回文和最大时对应的索引
                    if (max <= j - i + 1){
                        max = j - i + 1;
                        index = i;
                    }
                }
            }
        }
        return str.substring(index,max + index);
    }
}
